bonsoon's blog |
| latest | about | random
# Chebyshev function $\vartheta (x)$. Denote the prime counting function $$ \pi(x) = \sum_{p \le x} 1 $$where the sum is over the primes $p$. Denote the Chebyshev function $$ \vartheta(x) = \sum_{p \le x} \log(p) $$where the primes are weighted by its logarithm. Note that for all $x \ge 2$, $$ \vartheta(x) = \sum_{p \le x} \log(p) \le \sum_{p \le x}\log(x) = \pi(x) \log(x). $$ So we have $$ \begin{align*} \liminf \frac{\vartheta(x)}{x} &\le \liminf \frac{\pi(x)\log(x)}{x} \quad\text{and}\\ \limsup \frac{\vartheta(x)}{x} &\le \limsup \frac{\pi(x)\log(x)}{x} \end{align*} $$ Now, fix any $\delta \in (0,1)$. Note that for all $x \ge 2$, $$ \vartheta(x) = \sum_{p \le x} \log p \ge \sum_{x^{1 - \delta} < p \le x} \log p $$and as $x^{1-\delta} < p$, we have $(1- \delta) \log x < \log p$. So $$ \begin{align*} \vartheta(x) & \ge \sum_{x^{1-\delta} < p \le x} (1-\delta)\log (x) \\ & = (1-\delta) (\log x) ( \pi(x) - \pi(x^{1-\delta})). \end{align*}$$ Since naively, for positive $t$$$ \pi(t) \le t, $$ we have for $x \ge 2$, $$ \vartheta(x) \ge (1-\delta)\pi(x)\log(x) - x^{1-\delta}\log(x). $$ Whence for $x\ge 2$, $$ \frac{\vartheta(x)}{x} \ge (1-\delta) \frac{\pi(x)\log(x)}{x} - \frac{\log(x)}{x^{\delta}}. $$ Since $\log(x)/ x^{\delta} \to 0$ as $x \to \infty$ for $\delta > 0$, we see that $$ \begin{align*} \limsup \frac{\vartheta(x)}{x} &\ge(1-\delta) \limsup \frac{\pi(x)\log(x)}{x}\\ \text{and}\quad\limsup \frac{\vartheta(x)}{x} &\ge(1-\delta) \limsup \frac{\pi(x)\log(x)}{x} \end{align*} $$ Since this is true for all $\delta \in (0,1)$, we have $$ \begin{align*} \limsup \frac{\vartheta(x)}{x} &\ge \limsup \frac{\pi(x)\log(x)}{x}\\ \text{and}\quad\limsup \frac{\vartheta(x)}{x} &\ge \limsup \frac{\pi(x)\log(x)}{x}. \end{align*} $$ Combined with our earlier inequalities, we have $$ \begin{align*} \limsup \frac{\vartheta(x)}{x} & = \limsup \frac{\pi(x)\log(x)}{x}\\ \text{and}\quad\limsup \frac{\vartheta(x)}{x} &= \limsup \frac{\pi(x)\log(x)}{x}. \end{align*} $$so, bounding $\vartheta(x) / x$ is to bound $\pi(x) \log (x) / x$. Let us bound $\vartheta(x)/x$ from above. ## Central binomial coefficients and their prime factors. We make some observations of the central binomial coefficients $2n \choose n$, and see how it relates to primes. Denote $v_{p}(m)$ as the largest power $k$ such that $p^{k} \mid m$. In other words $v_{p}(m)=k$ where $p^{k} \parallel m$. This is sometimes called the $p$-adic valuation of $m$. Note we have a lemma of Legendre, for integer $n > 1$, we have $$ v_{p}(n!) = \sum_{k \ge 1} \left\lfloor \frac{n}{p^{k}} \right\rfloor . $$ Indeed, $$ \begin{align*} v_{p}(n!) &= \sum_{r=1}^{n} v_{p}(r) \\ &= \sum_{r=1}^{n} \sum_{k\ge 1} \mathbf{1}_{}\{p^{k} \mid r\} \\ &= \sum_{k\ge 1} \sum_{r=1}^{n} \mathbf{1}_{}\{p^{k} \mid r\} \\ \implies v_{p}(n!) &= \sum_{k \ge 1} \left\lfloor \frac{n}{p^{k}} \right\rfloor \end{align*} $$ Now, crudely we have $$ \frac{2^{2n}}{2n} \le {2n \choose n} \le 2^{2n}. $$ What can we say $v_{p}{2n \choose n}$, for integer $n\ge 1$ and $p$ some prime? If $p$ is a prime such that $n < p \le 2n$, then there is no other number $r$ that has $p$ as a factor where $n < r \le 2n$ besides $p$. In this case $$ v_{p} {2n \choose n} =1 $$when $n < p \le 2n$, since the denominator would have have any factors of $p$ at all. So by considering the prime factorization of $2n \choose n$, we have $$ {2n \choose n} = \prod_{p\le 2n} p^{v_{p}{2n \choose n}} \ge \prod_{n < p \le 2n} p. $$ So, for any integer $n \ge 1$, we have $$ \prod_{n < p \le 2n} p \le 2^{2n}. $$ Taking logs, we see that for integers $n \ge 1$, $$ \sum_{n< p \le 2n} \log p \le 2n \log(2) $$ Namely for all positive integers $n\ge 1$, $$ \vartheta(2n) - \vartheta(n) \le 2n \log(2). $$ On the other hand, for integer $n \ge 1$, $$ \begin{align*} {2n \choose n} = \frac{(2n)!}{n!n!} = \prod_{p \le 2n} p^{v_{p}((2n)!) - v_{p}(n!)-v_{p}(n!)} \\ \end{align*} $$ And $$ \begin{align*} v_{p}((2n)!)-2v_{p}(n!) &= \sum_{k\ge 1}^{\lfloor \log_{p}(2n) \rfloor} \left\lfloor \frac{2n}{p^{k}} \right\rfloor -2 \left\lfloor \frac{n}{p^{k}} \right\rfloor \\ &\le \lfloor \log_{p}(2n) \rfloor \end{align*} $$ since $\lfloor 2t \rfloor - 2 \lfloor t \rfloor \in \{0,1\}$ for all real $t$. So $$ \frac{2^{2n}}{2n} \le {2n \choose n} \le \prod_{p \le 2n} p^{\log_{p}(2n) }= (2n)^{\pi(2n)}. $$ In other words, for all $n\ge 1$, we have $$ \pi(2n)\log(2n) \ge 2n \log(2) - \log(2n). $$